package leetcode.editor.offer;

// 剑指 Offer 47. 礼物的最大价值
// https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/description/
class LiWuDeZuiDaJieZhiLcof {
    public static void main(String[] args) {
        Solution solution = new LiWuDeZuiDaJieZhiLcof().new Solution();
        // solution.maxValue(new int[][]{{1, 2, 5}, {3, 2, 1}});
        solution.maxValue(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public int maxValue(int[][] grid) {
            // dp[i][j]表示下标i-1和j-1的礼物的价值
            int[][] dp = new int[grid.length][grid[0].length];

            // 初始化
            dp[0][0] = grid[0][0];
            for (int i = 1; i < grid.length; i++) dp[i][0] = grid[i][0] + dp[i - 1][0];
            for (int i = 1; i < grid[0].length; i++) dp[0][i] = grid[0][i] + dp[0][i - 1];

            for (int i = 1; i < grid.length; i++) {
                for (int j = 1; j < grid[0].length; j++) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }

            return dp[grid.length - 1][grid[0].length - 1];
        }*/

        public int maxValue(int[][] grid) {
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (i == 0 && j == 0) continue;
                    if (i == 0) grid[0][j] += grid[0][j - 1];
                    else if (j == 0) grid[i][0] += grid[i - 1][0];
                    else grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
                }
            }

            return grid[grid.length - 1][grid[0].length - 1];
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
